package com.practice.search;

import java.util.HashSet;
import java.util.HashMap;

import com.practice.util.FileHelper;

public class LongestTransform {
	private final static String DIR = "src/test/resources/com/practice/search";
	
	public void find() {
		int N = 30;	
		String content = FileHelper.readFile(DIR + "/WORD.LST");
		String[] words = content.split("\n");
		HashSet<String>[] set = new HashSet[30];
		HashMap<String, String>[] map = new HashMap[N];
		for (int i=0; i<N; i++) {
			set[i] = new HashSet<String>();
			map[i] = new HashMap<String, String>();
		}
		
		for (String word : words) {
			set[word.length()].add(word);
		}
		
		
		for (String word : set[1]) {
			map[1].put(word, "");
		}
		
		int i=2;
		while (i < N) {
			for (String word : set[i]) {
				for (int j=0; j<word.length(); j++) {
					String shrink = word.substring(0, j) + word.substring(j+1);
					if (map[i-1].containsKey(shrink)) {
						map[i].put(word, shrink);
						break;
					}
				}
			}
			if (map[i].size() == 0) break;
			i++;
		}
		
		String word = map[i-1].keySet().iterator().next();
		for (int j=i-1; j>0; j--) {
			System.out.print(word + " - ");
			word = map[j].get(word);
		}
	}
	
	public static void main(String[] args) {
		new LongestTransform().find();
	}
}
